[数据结构与算法] 二叉树的应用

递归

“递归”是解决二叉树相关问题时常用的方法，在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归(recursive)调用。下面的代码就是利用递归求解斐波那契（Fibonacci）数列中的第n个数字：

int Fibonacci(int n)//定义fun函数
{
  int result;
  if (n > 2){
      // Fibonacci数列中第n项的值等于第n-1项的值+第n-2项的值
    result = Fibonacci(n - 1) + Fibonacci(n - 2);
  }
  else
    result = 1;//n=2时退出返回到main函数
  return result;

我们知道，树可以以递归的方式定义为一个节点（根节点），它包括一个值和一个指向其他节点指针的列表。递归是树的特性之一。因此，许多树问题可以通过递归的方式来解决。对于每个递归层级，我们只能关注单个节点内的问题，并通过递归调用函数来解决其子节点问题。

通常，我们可以通过 “自顶向下” 或 “自底向上” 的递归来解决树问题。

“自顶向下”的递归

“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。具体来说，递归函数 top_down(root, params) 的原理是这样的：

return specific value for null node
update the answer if needed                      // anwer <-- params
left_ans = top_down(root.left, left_params)      // left_params <-- root.val, params
right_ans = top_down(root.right, right_params)   // right_params <-- root.val, params
return the answer if needed                      // answer <-- left_ans, right_ans

“自底向上”的递归

“自底向上” 是另一种递归方法。在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。这个过程可以看作是后序遍历的一种。通常， “自底向上” 的递归函数 bottom_up(root) 为如下所示：

return specific value for null node
left_ans = bottom_up(root.left)          // call function recursively for left child
right_ans = bottom_up(root.right)        // call function recursively for right child
return answers                           // answer <-- left_ans, right_ans, root.val

运用递归解决树的问题

二叉树的最大深度

[LeetCode 104] 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

分析：直接运用“自顶向下”递归方法，代码如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL){
            return 0;
        }
        int left_Depth = maxDepth(root->left);
        int right_Depth = maxDepth(root->right);
        return max(left_Depth, right_Depth) + 1;
    }
};

对称二叉树

[LeetCode 101] 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。

分析：（设二叉树左子树为p，右子树为q，p、q均指向左右子树的根）
二叉树是对称的要满足：p和q的值相等，并且p的左子树与q的右子树对称，p的右子树与q的左子树对称，代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isMirror(root, root);
    }
    bool isMirror(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL && root2 == NULL){
            return true; //都是空
        }else if(root1 == NULL || root2 == NULL){
            return false; //只有一个是空
        }
        return (root1->val == root2->val) && isMirror(root1->left, root2->right) && isMirror(root1->right,root2->left);
    }
};

路径总和

[LeetCode 112] 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
分析：比较简单，直接看代码即可：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL)
            return false;
        if (root->left == NULL && root->right == NULL && root->val == sum)
            return true;     // 是叶子结点且路径和满足
        if (hasPathSum(root->left, sum-root->val))
            return true;
        if (hasPathSum(root->right, sum-root->val))
            return true;
        return false;
    }
};

填充同一层的兄弟节点

[LeetCode 116] 填充同一层的兄弟节点
给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将next指针设置为NULL。
初始状态下，所有next指针都被设置为 NULL。

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

分析：
当前节点左孩子的next指针应该指向当前节点的右孩子
当前节点右孩子的next指针应该指向当前节点next指针的左孩子（如果当前节点next为空，则指向NULL）

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root)
            return;
        if(root->left){
            root->left->next = root->right;
        }
        if(root->right){
            root->right->next = root->next? root->next->left : NULL;
        }
        connect(root->left);
        connect(root->right);
    }
};

[LeetCode 117] 填充同一层的兄弟节点 II
给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
说明:

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

分析：原本的完全二叉树的条件不再满足，但是整体的思路还是很相似，这里由于子树有可能残缺，故需要平行扫描父节点同层的节点，找到他们的左右子节点。代码如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *p = root->next;
        while (p) {
            if (p->left) {
                p = p->left;
                break;
            }
            if (p->right) {
                p = p->right;
                break;
            }
            p = p->next;
        }
        if (root->right) root->right->next = p; 
        if (root->left) root->left->next = root->right ? root->right : p; 
        connect(root->right);
        connect(root->left);
    }
};